package com.txy.sort;

/**
 * 计数排序 O(n+m)  n:数据个数 m:数据范围
 */
public class CountSort {
    public static int[] countSort(int[] arr, int offset) {
        int[] nums = new int[arr.length];
        for(int i=0;i<arr.length;i++) {
            int n =(arr[i]-offset);
            nums[n]++;
        }
        int[] nums2= new int[arr.length];
        for(int i=0,k=0;i<nums.length;i++) {
            for(int j=0;j<nums[i];j++){
                nums2[k++] = i+offset;
            }
        }
        return nums2;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{91,93,92,95,97,96,99,98,94};
        int[] res = countSort(arr, 91);
        System.out.println();
    }
}
